The present invention relates to layouts composed of geometrical objects, such as polygons, lines and points, and more specifically to a system and method for enforcing design rules and optimizing geometrical objectives for layouts in integrated circuits.
Prior to producing masks needed for the manufacture of integrated circuits (ICs), every IC layout must satisfy complex design rules specific to the IC manufacture technology. These design rules are usually geometric in nature, and may include, for example, minimum area, width, spacing, overlap and/or enclosure requirements on the IC layout. The rules generally apply to all regions of an IC layout and apply over a two dimensional space involving one or more layers. By obeying all design rules for a given IC technology and all circuit requirements of the IC design, such as connectivity, wire widths and device sizes, the IC layout will yield functional and manufacturable chips.
IC layouts are generally partitioned into a hierarchical structure involving cell masters, whereby cell masters are referenced by one or more cell instances, and each cell master in turn may contain layout objects and/or other cell instances. A hierarchical organization of an IC layout is needed to efficiently represent repeated structures and to manage large complex ICs or IC components. For highly regular layouts, array structures are used to represent rows and/or columns of repeated cell instances.
For most IC layouts, layout designers manually produce the cells composing a layout with the aid of graphical layout editors. Once drawn, the cells must be verified with design rule and circuit verification programs and altered to fix violations. This is a tedious and costly process and often must be repeated for every IC technology that will be used to manufacture chips containing the cells. The process of transforming an existing layout obeying design rules of some IC technology to a new layout obeying design rules of a different IC technology is called layout migration. Though layout migration is easier than the initial creation of a IC layout, it is usually done manually with layout designers since automation of layout migration is very difficult.
To date, the primary automation method applied to the problem of transforming an existing IC layout to a new layout obeying design rules of a target IC technology is compaction. Compaction is a method used to optimize a given IC layout subject to a set of design rule constraints. The layout is optimized by minimizing the total layout area as well as the length of wires and area of other layout objects. The layout objects are constrained by design rule interactions and circuit connectivity and parameter requirements and must be positioned without violating any such constraint. Almost all compaction methods are performed in one dimension at a time and often on one cell at time. This is done to simplify the compaction problem to the point that the problem can be solved by efficient solving algorithms. To completely compact a layout in two dimensions, compaction must be performed in the vertical direction, or Y direction in Cartesian coordinates, then the horizontal direction, or X direction in Cartesian coordinates. A layout could also be compacted first in the horizontal direction followed by compaction in the vertical direction.
Each time compaction is performed, four steps must be conducted. The first step is to model layout objects or layout object edges with position variables and define an objective function that is a weighted sum of position variables. The next step is to create constraints between layout objects or edges based on the design rules of the target IC technology and circuit requirements of the target IC design. The constraints are modeled as linear mathematical relations involving a two or more position variables. The third step is to solve the mathematical problem of minimizing the objective function subject to the linear constraint relations using a known linear program solving algorithm. The last step is to update the layout objects with the solution from the solving algorithm.
When compaction is performed in one dimension on a single cell, the compaction model defaults to a constraint graph problem, where nodes in the graph represent position variables and arcs in the graph represent linear constraints. The resulting problem can be solved with a Network Flow Simplex algorithm, which is very efficient in practice. Further details on compaction modeled with constraint graphs can be found in xe2x80x9cAn Efficient Compactor for 45xc2x0 Layoutxe2x80x9d, 25th Design Automation Conference, Anaheim, Calif., June 1988, pp. 396-402. When compaction is performed in one dimension on a hierarchical layout and the hierarchy is to be preserved, the compaction model is a general linear program, which can be solved by sparse implementations of the Revised Simplex algorithm. Further details on compaction modeled with linear programs can be found in xe2x80x9cA Hierarchy Preserving Hierarchical Compactorxe2x80x9d, 27th Design Automation Conference, Orlando, Fla., June 1990, pp. 375-381. Additional details on compaction can be found in xe2x80x9cLeaf Cell and Hierarchical Compaction Techniquesxe2x80x9d, by Cyrus Bamji and Ravi Varadarajan, Kluwer Academic Publishers, Norwell Mass., 1997.
Compacting a layout in one dimension at a time does not always produce the best result. Moreover, the result varies depending on which direction the first compaction is performed. Consider the example layout shown in FIG. 1(a). This layout contains four layout objects A, B, C and D which are all assigned the same layer and must be spaced apart by a minimum spacing design rule. If this layout is compacted in the vertical direction only, then in the horizontal direction only, the layout shown in FIG. 1(c) results. If the layout in FIG. 1(a) is compacted in the horizontal direction only, then in the vertical direction only, the layout shown in FIG. 1(b) results. The best result that is possible is shown in FIG. 1(d), which can not be easily produced by compacting in one dimension at a time. The layouts in FIGS. 1(b), 1(c) and 1(d) all obey the minimum spacing design rules of the target IC technology, but only the layout in FIG. 1(d) occupies the smallest area, which would be the lowest cost to manufacture.
Compacting a layout in both dimensions simultaneously usually produces better results than compacting in one dimension at a time. By compacting in two dimensions at once, the layout in FIG. 1(a) can be transformed to the layout in FIG. 1(d). However, one of the difficulties of two dimensional compaction methods is with corner to corner interactions. Examples of such interactions can be found in FIG. 1(a), namely the bottom right corner of layout object A to the top left corner of layout object B, the top right corner of layout object C to the bottom right corner of layout object B, and the bottom right corner of layout object B to the top left corner of layout object D. To date, two dimensional compaction methods handle corner to corner interactions with Branch and Bound or other expensive algorithms, which have execution times that grow exponentially with the size of the layout. Though these methods produce good results, these methods can only be applied to small layouts such as a single cell. Further details on two dimensional compaction methods can be found in xe2x80x9cEfficient Generation of Diagonal Constraints for 2-D Mask Compactionxe2x80x9d, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 15, No. 9, September 1996, pp. 1119-1126 and xe2x80x9cTwo-Dimensional Layout Compaction by Simulated Annealingxe2x80x9d, IEEE International Symposium on Circuits and Systems, August 1988, pp. 2439-2443.
Therefore, a need exists for a two dimensional compaction method that can handle large IC layouts efficiently and still yield quality results. Moreover, to handle even larger layouts with some regularity or repeated cell instances, a need exists for a two dimensional compaction method that operates on hierarchical layouts and preserves the layout hierarchy. For somewhat regular layouts using hierarchy, such a method would provide additional efficiency for layout migration and compaction. Another benefit of two dimensional compaction methods for large layouts with or without hierarchy is to simplify the usage of the compaction technology, since the user need not choose a starting direction as needed with one dimensional compaction methods.
The present invention relates to layouts with geometrical objects, and more particularly, to a system and method for compacting layouts in two dimensions simultaneously. In a particularly useful embodiment, the system and method of the present invention are applied to IC layouts. The present invention provides an efficient means for compacting layouts in two dimensions at once without depending on expensive methods such as Branch and Bound. As a result, the present invention can be applied to large layouts in much the same way as conventional, one dimensional compaction systems and methods.
The present invention also provides an efficient means for compacting hierarchical layouts in two dimensions at once while preserving the complete hierarchy. The present invention also solves the problem of preserving hierarchy with cell instances of the same cell master at orthogonal orientations to each other, which usually occurs with chip bonding pad circuits, sometimes referred to as Input/Output buffers.
The present invention also handles layout objects with edges at any angle and alters the length of all edges as part of two dimensional compaction. In a particularly useful embodiment of the present invention, edges are limited to 45xc2x0 multiple angles which stretch or shrink during compaction. The present invention also handles general circuit requirements, including device sizes that are a function of two dimensions. The present invention not only provides an elegant solution to the general compaction of hierarchical layout in two dimensions, it also finds quality solutions quickly and with no manual help or interaction.